# 数据流中的第K大元素：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/submissions/

class KthLargest:
    """ 又是一道典型的TopK的问题！ """

    def __init__(self, k: int, nums: list):
        self.k = k
        self.nums = nums
        self.heap = []
        # 初始化k长最小堆
        self.createHeapK()


    def createHeapK(self):
        """ 建立最小堆 """
        for num in self.nums:
            if len(self.heap) < self.k:
                self.heapPush(num)
            elif num > self.heap[0]:
                self.heap[0] = num
                self.heapAdjust()


    def heapAdjust(self):
        """ 调整堆 """
        i = 0
        end = self.k - 1
        rc = self.heap[0]
        while i * 2 + 1 <= end:
            j = i * 2 + 1
            if j < end and self.heap[j] > self.heap[j + 1]: j += 1
            if self.heap[j] > rc: break
            self.heap[i] = self.heap[j]
            i = j
        
        self.heap[i] = rc


    def heapPush(self, num):
        """ 堆中添加元素,这个是建立 k长堆时调用 """
        self.heap.append(num)
        i = len(self.heap) - 1
        while (i - 1) // 2 >= 0:
            j = (i - 1) // 2
            if self.heap[j] < num: break
            self.heap[i] = self.heap[j]
            i = j
        
        self.heap[i] = num


    def add(self, val: int) -> int:
        self.nums.append(val)
        if len(self.heap) < self.k:
                self.heapPush(val)
        elif val > self.heap[0]:
            self.heap[0] = val
            self.heapAdjust()

        return self.heap[0]


# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)